class Solution1:
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2


class Solution2:
    def removeElement(self, nums, val):
        """双指针形式"""
        a = 0
        b = 0
        while a < len(nums):
            if nums[a] != val:
                nums[b] = nums[a]
                b += 1
            a += 1
        return b

    def climbStairs(self, n: int) -> int:
        # dp[i]表示爬到第i级楼梯的种数， (1, 2) (2, 1)是两种不同的类型
        dp = [0] * (n + 1)
        print("dp:", dp)
        dp[0] = 1
        for i in range(n + 1):
            for j in range(1, 3):
                if i >= j:
                    dp[i] += dp[i - j]
                    print(dp)
        return dp[-1]

    def strStr(self, haystack, needle):
        if needle not in haystack:
            return -1
        elif needle == '':
            return 0
        else:
            for i in range(len(haystack)):
                print(haystack[i:len(needle) + i])
                print("目标值是：",needle[:])
                if haystack[i:len(needle) + i] == needle:
                    return i

    def maxSubArray(self, nums) :
        for i in range(1, len(nums)):
            nums[i] = max(nums[i - 1] + nums[i], nums[i])
            print(nums[i])
            print(nums)
        return max(nums)





if __name__ == '__main__':
    a = Solution2()
    l1 = [1, 2, 4]
    l2 = [1, 3, 4]
    # print(a.strStr('aaahahahaha', 'hah'))
    print(a.maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))
